Мутация белка - 2

Максимальная оценка за эту задачу — 60 баллов. Учитывается последняя посылка!

В этой задаче мультитест и другие ограничения (см. раздел «Входные данные»). Условие задачи и форматы ввода и вывода полностью совпадают с предыдущей задачей, однако в этой задаче вам необходимо сдать на проверку текстовый файл с ответом на конкретный тест, который вы должны сгенерировать на своем компьютере. Скачать файл со входными данными для этой задачи вы можете нажав на ссылку «Скачать условие задачи» внизу этой страницы (после раздела «Система оценивания»).

Во время тура ответ будет проверяться только на соответствие формату, проверка с выставлением баллов будет осуществляться после окончания тура. Статус OK и 0 баллов во время тура означает, что сданный вами файл соответствует формату и будет проверен после тура, в случае других статусов файл не соответствует формату и вам следует проверить и исправить его.

РНК можно рассматривать как длинную цепочку, составленную из нуклеотидов. В этой задаче нуклеотидом будем называть один из символов ‘U’, ‘C’, ‘A’, ‘G’. Три подряд идущих нуклеотида образуют кодон (порядок нуклеотидов в кодоне важен). Каждому кодону соответствует некоторая аминокислота, при этом нескольким различным кодонам может соответствовать одна и та же аминокислота:

image
Соответствие кодонов аминокислотам

Выберем первый нуклеотид в центре, далее будем переходить на следующее кольцо по соответствующему нуклеотиду, соседнему со стороной фигуры.

Например, «AUG» — это кодон, который соответствует аминокислоте ‘M’.

Обратите внимание, что старт кодон выглядит как «AUG», а стоп кодон — это один из вариантов: «UAA», «UAG», «UGA».

Будем говорить, что белок — это последовательность аминокислот, которая начинается с аминокислоты ‘M’ и заканчивается одной из аминокислот, являющихся стоп-кодоном (такие аминокислоты обозначены в таблице кружком). Стоп-кодон не может встречаться в середине белка. Аминокислота ‘M’, напротив, может встречаться несколько раз.

Биолог исследует белок длины n n . При синтезе РНК произошла ошибка: в неё было вставлено ещё k k нуклеотидов в произвольные места. В результате получилась последовательность из 3 n + k 3n + k нуклеотидов, и биолог хочет восстановить какой-нибудь белок длины n n .

Формат ввода

В первой строке записано одно целое число t t  — количество тестов. В этой версии задачи t = 20 t=20 .

Во 2 ⋅ ( t + 1 ) 2\cdot (t + 1) -й строке записаны два целых числа n n и k k ( 2 ≤ n ≤ 1 05 2 \le n \le 10^5 , 1 ≤ k ≤ 1 05 1 \le k \le 10^5 ).

В 2 ⋅ ( t + 1 ) + 1 2\cdot (t + 1) + 1 -й строке записана строка длины 3 n + k 3n + k , которая является последовательностью нуклеотидов. Гарантируется, что строка содержит только символы ‘U’, ‘C’, ‘A’, ‘G’.

Формат вывода

Выведите t t строк, в каждой из них k k различных целых чисел — номера удаляемых нуклеотидов в тесте t t . Номера можно выводить в любом порядке.

Система оценивания

Длина восстановленного белка l e n len определяется следующим образом.

Рассмотрим строку, полученную после удаления некоторых нуклеотидов, и разобьём её на кодоны. Затем найдём первое вхождение старт-кодона и первое вхождение стоп-кодона, расположенное после него. Тогда длиной белка будем считать количество аминокислот от ‘M’ до этого стоп-кодона включительно.

Количество баллов за тест определяется по формуле s c o r e = l e n n ⋅ 3. score = \frac{len}{n} \cdot 3.

Обратите внимание, что если у вас выполнится одно из трёх условий:

  1. Нет ни одного старт кодона;

  2. Нет ни одного стоп кодона;

  3. Все старт кодоны находятся после всех стоп кодонов;

то вы получите 0 0 баллов за тест.

Примечания

Для удобства обозначим стоп кодон как ‘e’.

В первом примере после удаления нуклеотидов под номером 3 3 получим последовательность нуклеотидов AUGUGA, разобьём её на кодоны AUG, UGA — это соответствует белку Me. Его длина равна 2.